package hot100;


/*
 * Author：江松
 * Date：2023/4/12 10:34
 *
 *
 根据身高重建队列:
 1,排序，模拟 O(nLogN+n*n)
 关于排序：要么在Arrays.sort中实现Comparator，要么在自定义类中实现Comparable
 将身高降序排列，k升序排列，然后插空
 */



import java.util.*;

public class Main406 {


    public int[][] reconstructQueue(int[][] people) {
        int n=people.length,m=people[0].length;

        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return o1[1]-o2[1];
                }
                return o2[0]-o1[0];
            }
        });

        List<int[]>tmp=new LinkedList<>();
        for(int i=0;i<n;++i){
            tmp.add(people[i][1],people[i]);
        }
        return tmp.toArray(new int[n][]);
    }


    public static void main(String[] args) {
        int people[][]=new int[6][2];
        people[0][0]=7;
        people[0][1]=0;
        people[1][0]=4;
        people[1][1]=4;
        people[2][0]=7;
        people[2][1]=1;
        people[3][0]=5;
        people[3][1]=0;
        people[4][0]=6;
        people[4][1]=1;
        people[5][0]=5;
        people[5][1]=2;
        int res[][]=new Main406().reconstructQueue(people);
        for(int i=0;i<res.length;++i){
            System.out.printf("%d %d\n",res[i][0],res[i][1]);
        }
    }
}
